首页 > 试题广场 >

矩阵的最小路径和

[编程题]矩阵的最小路径和

热度指数：86073 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: $1 \le n,m\le 500$ ，矩阵中任意值都满足 $0 \le a_{i,j} \le 100$

要求：时间复杂度 $O(nm)$

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，

所选择的最小累加和路径如下图所示：

示例1

输入

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

输出

示例2

输入

[[1,2,3],[1,2,3]]

输出

备注:

算法知识视频讲解

Python 3

Virtual~

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        m, n = len(matrix), len(matrix[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = matrix[0][0]

        for i in range(1, m):
            dp[i][0] = matrix[i][0] + dp[i-1][0]
        for j in range(1, n):
            dp[0][j] = matrix[0][j] + dp[0][j-1]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]

        return dp[-1][-1]

发表于 2022-09-19 16:08:14 回复(0)

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        #本题的关键在于单独考虑第一行，第一列
        m=len(matrix)
        n=len(matrix[0])
        if m==0 and n==0:
            return 0
        dp=[[0]*n for i in range(m)]
        dp[0][0]=matrix[0][0]
        #必须单独处理
        for i in range(1, n):
            dp[i][0] = matrix[i][0] + dp[i - 1][0]
        #处理第一行
        for j in range(1, m):
            dp[0][j] = matrix[0][j] + dp[0][j - 1]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=min(matrix[i][j]+dp[i-1][j],matrix[i][j]+dp[i][j-1])
        print(dp)
        return dp[m-1][n-1]

发表于 2022-08-21 16:32:31 回复(0)

Python 3

准备回家种田的程序猿

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        '''
        #同不同路径的数目，我们可以建立一个二维的dp数组，保存到达
        当前位置的最小路径和，同样，可由左边或者上边到达当前位置
        所以：
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j] (i>=1 j>=1)
            
        
        '''
        m,n=len(matrix),len(matrix[0]) #m行 n列
        dp=[list(matrix[i]) for i in range(m)]
        
        #特殊值更新 更新第一行的数据
        for i in range(1,n):
            dp[0][i]+=dp[0][i-1]
        
        #特殊值更新 更新第一列的数据
        for j in range(1,m):
            dp[j][0]+=dp[j-1][0]
        
        for i in range(1,m):
            for j in range(1,n):
                
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
        return dp[i][j]

发表于 2022-08-15 16:52:10 回复(0)

Python 3

霸气青提

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        for i in range(1, len(matrix)):
            matrix[i][0] += matrix[i-1][0]
        for j in range(1, len(matrix[0])):
            matrix[0][j] += matrix[0][j-1]
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1])
        return matrix[-1][-1]

发表于 2022-07-26 10:31:56 回复(0)

Python 3

lun__

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        m = len(matrix) 
        n = len(matrix[0]) 
        
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = matrix[0][0] 
        
        ## dp数组初始化！！，一定要再回头看看dp的含义！！ 
        for i in range(1, m): 
            dp[i][0] = matrix[i][0] + dp[i - 1][0]
        
        for j in range(1, n): 
            dp[0][j] = matrix[0][j] + + dp[0][j - 1]
        
        for i in range(1, m): 
            for j in range(1, n): 
                dp[i][j] += min(dp[i-1][j], dp[i][j-1]) + matrix[i][j] 
        
        print(dp) 
        return dp[-1][-1]

发表于 2022-07-25 09:57:24 回复(1)

Python 3

Vivimore

时间复杂度：O(mn) 空间复杂度O(mn)

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        dp = [[0]*(m+1) for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if i == 1:
                    dp[i][j] = dp[i][j-1] + matrix[i-1][j-1]
                    continue
                if j == 1:
                    dp[i][j] = dp[i-1][j] + matrix[i-1][j-1]
                    continue
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i-1][j-1]
        return dp[n][m]

发表于 2022-05-22 10:20:59 回复(0)

Python 3

我不配346

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        if not matrix:
            return 0
        row = len(matrix)
        col = len(matrix[0])
        dp = [col * [0] for i in range(row)]
        dp[0][0] = matrix[0][0]
        for i in range(1, row):
            dp[i][0] = dp[i-1][0] + matrix[i][0]
        for i in range(1, col):
            dp[0][i] = dp[0][i-1] + matrix[0][i]
        for i in range(1, row):
            for j in range(1, col):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
        return dp[row-1][col-1]

发表于 2022-04-09 17:40:18 回复(0)

Python 3

Joy_9

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        m=len(matrix)
        n=len(matrix[0])
        for i in range(m):
            for j in range(n):
                if i==0 and j==0:
                    matrix[i][j]=matrix[i][j]
                elif i ==0:
                    matrix[i][j]=matrix[i][j-1]+matrix[i][j]
                elif j ==0:
                    matrix[i][j]=matrix[i-1][j]+matrix[i][j]
                else:
                    matrix[i][j]=matrix[i][j]+min(matrix[i][j-1],matrix[i-1][j])
        return matrix[m-1][n-1]

发表于 2021-12-28 11:23:35 回复(0)

Python 3

长歌行abc

w=input()
w=eval(w)
dp=[]
m=len(w)
n=len(w[0])
dp=[[0 for _ in range(n)]for _ in range(m)]
dp[0][0]=w[0][0] for i in range(1,n):
    dp[0][i]=w[0][i]+dp[0][i-1] for j in range(1,m):
    dp[j][0]=w[j][0]+dp[j-1][0] for i in range(1,m): for j in range(1,n):
        dp[i][j]=min(dp[i-1][j],dp[i][j-1])+w[i][j] print(dp[m-1][n-1])

发表于 2021-10-17 20:06:46 回复(0)

Python 3

kotoriii

简简单单滴动态规划

#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix ):
        
        n=len(matrix)
        m=len(matrix[0])
        dp=[[0]*m for i in range(n)]
        
        for i in range(n):
            for j in range(m):
                if i==0 and j==0:
                    dp[i][j]=matrix[i][j]
                elif i==0 and j!=0:
                    dp[i][j]=dp[i][j-1]+matrix[i][j]
                elif i!=0 and j==0:
                    dp[i][j]=dp[i-1][j]+matrix[i][j]
                else:
                    dp[i][j]=min(dp[i][j-1]+matrix[i][j],dp[i-1][j]+matrix[i][j])
        return dp[n-1][m-1]
        # write code here

发表于 2021-09-14 23:00:38 回复(0)

Python 3

牛客38477449号

class Solution:
    def minPathSum(self , matrix ):
        # write code here
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        dp[0][0] = matrix[0][0]
        for j in range(1, len(matrix[0])):
            dp[0][j] = dp[0][j-1] + matrix[0][j]
        for i in range(1, len(matrix)):
            dp[i][0] = dp[i-1][0] + matrix[i][0]
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

发表于 2021-09-13 18:28:50 回复(0)

Python 3

VincentLau~

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid&nbs***bsp;not grid[0]:
            return 0
        
        rows, columns = len(grid), len(grid[0])
        dp = [[0] * columns for _ in range(rows)]
        dp[0][0] = grid[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, columns):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, rows):
            for j in range(1, columns):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        
        return dp[rows - 1][columns - 1]

发表于 2021-08-30 10:21:50 回复(0)